binary-search-insert

binary-search-insert

A library for performing a binary search and insert into a sorted array.
Binary search has an average time complexity of O(log(n)) which is substantially faster than a linear search with an average time complexity of O(n).

Installing

$ npm install binary-search-insert

Usage

var binarySearchInsert = require('binary-search-insert');
var sortedArray = [1, 3, 5, 7, 9, 11];
var comparator = function (a, b) { return a - b; }

/**
 * Mutates sortedArray and returns index of inserted value
 * @param {Array} A sorted array
 * @param {*} An item to insert in the sorted array
 * @param {Function} A comparator function that takes two arguments and returns a number. The first
 *   argument will be a member of sortedArray, the second argument will be item.
 *   If item < member, return value < 0
 *   If item > member, return value > 0
 * @returns {Number} index of array where item is inserted
 */
var indexInsertedAt = binarySearchInsert(sortedArray, comparator, 6);
// indexInsertedAt: 3
// sortedArray: [1, 3, 5, 6, 7, 9, 11]

Benchmarks

http://jsperf.com/cflynn07-binary-search-insert-vs-linear-search-insert

Testing

// Tests + coverage reports are run using Lab
$ npm test
// Test coverage reports
$ npm run test-cov # will auto-open Google Chrome with html coverage report

License

MIT